//题目:
// 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
// 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
// 返回获得利润的最大值。
// 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        //第i天结束后，可以有两种状态，即：“买入”和“卖出”

        //1.创建dp细化表
        vector<int> f(prices.size());//第i天结束后，“买入”状态所拥有的最大利润
        vector<int> g(prices.size());//第i天结束后，“卖出”状态所拥有的最大利润
        //2.初始化
        f[0]=0-prices[0]-fee,g[0]=0;
        //3.填表————动态转移方程：  f[i]=max(f[i-1],g[i-1]-prices[i]-fee)  （昨天是“买入” && 今天没卖） || （昨天是“卖出” && 今天买入）   
        //                        g[i]=max(f[i-1]+prices[i],g[i-1])  (昨天是“买入” && 今天把它卖了) || (昨天是“卖出” && 今天没买)
        for(int i=1;i<prices.size();i++)
        {
            f[i]=max(f[i-1],g[i-1]-prices[i]-fee);
            g[i]=max(f[i-1]+prices[i],g[i-1]);
        }
        //4.确定返回值
        int ret1=f[prices.size()-1];
        int ret2=g[prices.size()-1];
        return ret1>ret2?ret1:ret2;
    }
};

